package 图论;

/**
 * @author huu
 * @create 2025-09-07-10:36
 * 结构
 * 前缀树是一种树结构，用于包含字符串集合
 * 根节点不包含字符，其它所有节点都只包含一个字符
 * 从根结点出发寻找子节点，找到叶节点代表这是一个完整的字符串
 * 从根节点出发寻找子节点，未到叶节点代表这是字符串集合的一个前缀或一个完整字符串
 * 操作方法
 * 插入一个字符串
 * 寻找一个字符串
 * 寻找一个前缀(字符串前面的一部分字符)
 * 如何判断找到的是前缀还是字符串呢
 * 加一个判断字段，isEnd，对于存入的每个单词的最后一个字母节点标记为true，这样就可以判断未到叶节点的路径是不是完整字符串了
 */
class Trie {
    class TrieNode{
        private boolean isEnd;
        private TrieNode[] children;
        public TrieNode(){
            isEnd = false;
            children = new TrieNode[26];
        }
    }
    public TrieNode root;
    public Trie(){
        root = new TrieNode();
    }
    public void insert(String word) {
        TrieNode cur = root;//指针
        //遍历字母向下存
        for(char c : word.toCharArray()){
            int index = c - 'a';
            if(cur.children[index] == null){
                cur.children[index] = new TrieNode();
            }
            cur = cur.children[index];
        }
        cur.isEnd = true;//标记这是一个完整的单词
    }

    public boolean search(String word) {
        TrieNode cur = root;
        for(char c : word.toCharArray()){
            int index = c - 'a';
            if(cur.children[index] == null){
                return false;
            }
            cur = cur.children[index];
        }
        return cur.isEnd;
    }

    public boolean startsWith(String prefix) {
        // 相比较search少了一个isEnd的判断而已
        TrieNode cur = root;
        for(char c : prefix.toCharArray()){
            int index = c - 'a';
            if(cur.children[index] == null){
                return false;
            }
            cur = cur.children[index];
        }
        return true;
    }
}
